package hash.leetcode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @Description: 无重复字符的最长子串
 * @Author Stark
 * @Date 2022/3/17 16:50
 **/
public class Num3_lengthOfLongestSubstring {
    public static int lengthOfLongestSubstring(String s) {
//        Map<Character,Integer> map = new HashMap<>();
//        Set<Character> set = new HashSet<>();
//        int end,newStart,maxLength;
//        end = newStart = maxLength = 0;
//        boolean flag = true;
//        while(end < s.length()){
//            char ch = s.charAt(end);
//            if(set.add(ch)){
//                map.put(ch,end);
//                end++;
//                if(flag)
//                    maxLength = end;
//            }else {
//                flag = false;
//                newStart = map.get(ch);
//                if (maxLength < set.size()) {
//                    maxLength = set.size();
//                }
//                end = ++newStart;
//                set.clear();
//            }
//        }
//        if(set.size() > maxLength){
//            maxLength = set.size();
//        }
//        return maxLength;

        //滑动窗口法(使用map)
//        if (s.length()==0) return 0;
//        HashMap<Character, Integer> map = new HashMap<>();
//        int max = 0;
//        //存储下一个不相同区间的开始下标
//        int left = 0;
//        for(int i = 0; i < s.length(); i ++){
//            //存在相同的值
//            if(map.containsKey(s.charAt(i))){
//                //更新下标,取最大值是为了保证区间里无重复值
//                //始终保存下一个不相等区间的开始下标
//                left = Math.max(left,map.get(s.charAt(i)) + 1);
//            }
//            //更新相同值的下标
//            map.put(s.charAt(i),i);
//            //获取最大的长度
//            max = Math.max(max,i-left+1);
//        }
//        return max;

        //滑动窗口法(使用数组)
        if(s.length() == 0)
            return 0;
        int start = 0,end = 0,maxLength = 0;
        int[] map = new int[256];
        map[(int)s.charAt(end++)] = 1;
        for (;end < s.length();end++){
            maxLength = Math.max(maxLength,end - start);
            while(map[s.charAt(end)] != 0){
                map[s.charAt(start++)] = 0;
            }
            map[s.charAt(end)] = 1;
        }
        maxLength = Math.max(end - start,maxLength);
        return maxLength;
    }

    public static void main(String[] args) {
        String str = "abcbacbb";
        System.out.println(lengthOfLongestSubstring(str));
    }
}
